package org.example.myleet.p1738;

import java.util.Arrays;

/**
 * 66 ms
 * 前缀和
 */
public class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length, ri = 0;
        int[] result = new int[m * n];
        int[][] sum = new int[m][n];
        sum[0][0] = matrix[0][0];
        result[ri++] = sum[0][0];
        for (int i = 1; i < m; ++i) {
            sum[i][0] = sum[i - 1][0] ^ matrix[i][0];
            result[ri++] = sum[i][0];
        }
        for (int j = 1; j < n; ++j) {
            sum[0][j] = sum[0][j - 1] ^ matrix[0][j];
            result[ri++] = sum[0][j];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                sum[i][j] = sum[i - 1][j] ^ sum[i][j - 1] ^ sum[i - 1][j - 1] ^ matrix[i][j];
                result[ri++] = sum[i][j];
            }
        }
        Arrays.sort(result);
        return result[m * n - k];
    }
}
